﻿/*

The MIT License

Copyright (c) 2010 Cartesian Analytics, Inc. 

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;

namespace Pipra.Uom
{
    /// <summary>
    /// A unit of measure graph.
    /// </summary>
    public class UomGraph :
        Collection<IUomAuthority>
    {
        /// <summary>
        /// The unit comparer used.
        /// </summary>
        public readonly UomComparer Comparer;
        /// <summary>
        /// Constructs a new UoM graph with the given <paramref name="authorities"/> matching the given comparer.
        /// </summary>
        /// <param name="authorities">The UoM authorities to use.</param>
        /// <param name="cmp">The comparer.</param>
        public UomGraph(IEnumerable<IUomAuthority> authorities, UomComparer cmp)
            : base(null == authorities ? new List<IUomAuthority>() : new List<IUomAuthority>(authorities))
        {
            Comparer = cmp ?? (Count > 0 ? this[0].Comparer : new UomComparer());
            if (this.Any(auth => auth.Comparer != Comparer))
            {
                throw new ArgumentException("Comparers do not match.", "authorities");
            }
        }
        /// <summary>
        /// Clears any cached data.
        /// </summary>
        public void ClearCache()
        {
        }

        protected override void ClearItems()
        {
            ClearCache();
            base.ClearItems();
        }

        protected override void InsertItem(int index, IUomAuthority item)
        {
            ClearCache();
            base.InsertItem(index, item);
        }

        protected override void RemoveItem(int index)
        {
            ClearCache();
            base.RemoveItem(index);
        }

        protected override void SetItem(int index, IUomAuthority item)
        {
            ClearCache();
            base.SetItem(index, item);
        }

        /// <summary>
        /// Gets a unit by name.
        /// </summary>
        /// <param name="type">The unit type.</param>
        /// <param name="name">The unit name.</param>
        /// <returns>A unit.</returns>
        public IUom GetUnit(string type, string name)
        {
            bool hasAuths = false;
            foreach (IUomAuthority uomAuth in this.Where(uomAuth => uomAuth.Type == type))
            {
                hasAuths = true;
                IUom uom = uomAuth.GetUnit(name);
                if(null != uom)
                {
                    return uom;
                }
            }
            if(!hasAuths)
            {
                throw new ArgumentException("Given uom type is not supported.", "type");
            }
            return null;
        }
        /// <summary>
        /// Fonds a conversion path from one unit to another.
        /// </summary>
        /// <param name="type">The unit type.</param>
        /// <param name="fromId">The unit to convert from.</param>
        /// <param name="toId">The unit to convert to.</param>
        /// <returns>A value converter.</returns>
        public IValueConverter<double> FindPath(string type, string fromId, string toId)
        {
            IUom from = GetUnit(type, fromId);
            if (null == from)
            {
                throw new ArgumentException("Unit not found.", "fromId");
            }
            IUom to = GetUnit(type, toId);
            if(null == to)
            {
                throw new ArgumentException("Unit not found.", "toId");
            }
            return FindPath(type, from, to);
        }

        private class NodeInfo
        {
            public int Distance;
            public IUom Predecessor;
            public IValueConverter<double> Used;

            public NodeInfo(int distance, IUom predecessor = null, IValueConverter<double> used = null)
            {
                Distance = distance;
                Predecessor = predecessor;
                Used = used;
            }
        }
        /// <summary>
        /// Fonds a conversion path from one unit to another.
        /// </summary>
        /// <param name="type">The unit type.</param>
        /// <param name="from">The unit to convert from.</param>
        /// <param name="to">The unit to convert to.</param>
        /// <returns>A value converter.</returns>
        public IValueConverter<double> FindPath(string type, IUom from, IUom to)
        {
            List<IUomAuthority> authorities = this.Where(uomAuth => uomAuth.Type == type).ToList();
            if(0 == authorities.Count)
            {
                return null;
            }
            List<IUom> units = authorities
                .SelectMany(uomAuth => uomAuth.Units)
                .Distinct(Comparer)
                .ToList()
            ;
            if(0 == units.Count)
            {
                return null;
            }

            List<IUom> unvisitedNodes = new List<IUom>(units);
            Dictionary<IUom, NodeInfo> nodeInfos = new Dictionary<IUom, NodeInfo>(unvisitedNodes.Count, Comparer);
            foreach(IUom unvisitedNode in unvisitedNodes)
            {
                nodeInfos[unvisitedNode] = new NodeInfo(Int32.MaxValue);
            }
            if(!nodeInfos.ContainsKey(from) || !nodeInfos.ContainsKey(to))
            {
                return null;
            }
            nodeInfos[from].Distance = 0;

            while(0 != unvisitedNodes.Count)
            {
                KeyValuePair<IUom, NodeInfo> bestNode = new KeyValuePair<IUom, NodeInfo>(null,new NodeInfo(Int32.MaxValue));
                for(int i = 0; i < unvisitedNodes.Count; i++)
                {
                    NodeInfo currentNodeInfo = nodeInfos[unvisitedNodes[i]];
                    if (currentNodeInfo.Distance < bestNode.Value.Distance)
                    {
                        bestNode = new KeyValuePair<IUom, NodeInfo>(
                            unvisitedNodes[i],
                            currentNodeInfo
                        );
                    }
                }

                if (bestNode.Value.Distance == Int32.MaxValue)
                {
                    break;
                }
                unvisitedNodes.Remove(bestNode.Key);

                Dictionary<IUom, IValueConverter<double>> toMap = GenerateToMap(bestNode.Key, authorities);

                foreach (IUom neighbor in toMap.Keys.Where(uom => unvisitedNodes.Contains(uom, Comparer)))
                {
                    IValueConverter<double> op = toMap[neighbor];
                    int calculatedDistance = bestNode.Value.Distance + op.OpCost + 1;
                    NodeInfo neighborInfo = nodeInfos[neighbor];
                    if (calculatedDistance < neighborInfo.Distance)
                    {
                        neighborInfo.Distance = calculatedDistance;
                        neighborInfo.Predecessor = bestNode.Key;
                        neighborInfo.Used = op;

                    }
                }
            }

            List<KeyValuePair<IUom, IValueConverter<double>>> path = new List<KeyValuePair<IUom, IValueConverter<double>>>();
            IUom pathNode = to;
            while (null != pathNode)
            {
                NodeInfo nodeInfo = nodeInfos[pathNode];
                path.Insert(0, new KeyValuePair<IUom, IValueConverter<double>>(pathNode, nodeInfo.Used));
                pathNode = nodeInfo.Predecessor;
            }

            IEnumerator<KeyValuePair<IUom, IValueConverter<double>>> nodeEnum = path.GetEnumerator();
            if(nodeEnum.MoveNext()) // skip the first
            {
                IUom pathFrom = nodeEnum.Current.Key;
                var converters = new List<IValueConverter<double>>(path.Count - 1);
                while(nodeEnum.MoveNext())
                {
                    IUom pathTo = nodeEnum.Current.Key;
                    IValueConverter<double> current = nodeEnum.Current.Value;
                    if (Comparer.Equals(current.From, pathFrom) && Comparer.Equals(current.To, pathTo))
                    {
                        converters.Add(current);
                    }else
                    {
                        throw new InvalidOperationException("The calculated conversion path is invalid.");
                    }
                    pathFrom = pathTo;
                }
                return new ValueConverterList(converters);
            }

            return null;


        }

        private Dictionary<IUom, IValueConverter<double>> GenerateToMap(IUom from, List<IUomAuthority> authorities)
        {
            Dictionary<IUom, IValueConverter<double>> toMap = new Dictionary<IUom, IValueConverter<double>>(Comparer);
            foreach(IUomAuthority authority in authorities)
            {
                foreach(IUom neighbor in authority.GetMappedUnits(from))
                {
                    IValueConverter<double> newConv = authority.GetConverter(from, neighbor) as IValueConverter<double>;
                    bool replace = !toMap.ContainsKey(neighbor) || toMap[neighbor].OpCost > newConv.OpCost;
                    if(replace)
                    {
                        toMap[neighbor] = newConv;
                    }
                }
            }
            return toMap;
        }

    }
}
